// Magic Software, Inc.
// http://www.magic-software.com
// Copyright (c) 2000, All Rights Reserved
//
// Source code from Magic Software is supplied under the terms of a license
// agreement and may not be copied or disclosed except in accordance with the
// terms of that agreement.  The various license agreements may be found at
// the Magic Software web site.  This file is subject to the license
//
// RESTRICTED USE SOURCE CODE
// http://www.magic-software.com/License/restricted.pdf

#include "MgcBox3.h"
#include "MgcCamera.h"
#include "MgcFrustum.h"
#include "MgcTerrainBlock.h"
#include "MgcTerrainPage.h"
#include "MgcTerrainVertex.h"

//---------------------------------------------------------------------------
void MgcTerrainBlock::GetVertex9 (unsigned short usSize,
    MgcTerrainVertex* pkVOrigin, MgcTerrainVertex* apkTVertex[9])
{
    unsigned short usOrigin = m_ucX+usSize*m_ucY;
    unsigned short usTwoStride = 2*m_ucStride;
    unsigned short usSizePlus1 = usSize+1;
    unsigned short usSizePlus2 = usSize+2;
    unsigned short usTwoSizePlus1 = 2*usSize+1;
    unsigned short usSizeTimesStride = usSize*m_ucStride;
    unsigned short usSizePlus1TimesStride = usSizePlus1*m_ucStride;
    unsigned short usSizePlus2TimesStride = usSizePlus2*m_ucStride;
    unsigned short usSizeTimesTwoStride = usSize*usTwoStride;
    unsigned short usTwoSizePlus1TimesStride = usTwoSizePlus1*m_ucStride;
    unsigned short usSizePlus1TimesTwoStride = usSizePlus1*usTwoStride;

    pkVOrigin += usOrigin;
    apkTVertex[0] = &pkVOrigin[0];
    apkTVertex[1] = &pkVOrigin[m_ucStride];
    apkTVertex[2] = &pkVOrigin[usTwoStride];
    apkTVertex[3] = &pkVOrigin[usSizeTimesStride];
    apkTVertex[4] = &pkVOrigin[usSizePlus1TimesStride];
    apkTVertex[5] = &pkVOrigin[usSizePlus2TimesStride];
    apkTVertex[6] = &pkVOrigin[usSizeTimesTwoStride];
    apkTVertex[7] = &pkVOrigin[usTwoSizePlus1TimesStride];
    apkTVertex[8] = &pkVOrigin[usSizePlus1TimesTwoStride];
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::Initialize (MgcTerrainPage* pkPage,
    MgcTerrainBlock* pkBlock, unsigned short usBlock, unsigned char ucX,
    unsigned char ucY, unsigned char ucStride, bool bEven)
{
    m_ucX = ucX;
    m_ucY = ucY;
    m_ucStride = ucStride;
    m_ucFlags = 0;
    m_fDeltaL = 0.0;
    m_fDeltaH = MgcMath::INFINITY;
    SetEven(bEven);

    MgcTerrainVertex* akTVertex[9];
    GetVertex9(pkPage->m_usSize,pkPage->m_akTVertex,akTVertex);

    // set vertex dependencies
    akTVertex[1]->SetDependent(0,akTVertex[4]);
    akTVertex[3]->SetDependent(1,akTVertex[4]);
    akTVertex[5]->SetDependent(0,akTVertex[4]);
    akTVertex[7]->SetDependent(1,akTVertex[4]);
    if ( bEven )
    {
        akTVertex[4]->SetDependent(0,akTVertex[6]);
        akTVertex[4]->SetDependent(1,akTVertex[2]);
    }
    else
    {
        akTVertex[4]->SetDependent(0,akTVertex[0]);
        akTVertex[4]->SetDependent(1,akTVertex[8]);
    }

    // recurse on children (if any)
    if ( ucStride > 1 )
    {
        // child stride is half the parent stride
        unsigned char ucChildStride = ( ucStride >> 1 );

        // process child 00
        unsigned short usChild = GetChildIndex(usBlock,1);
        MgcTerrainBlock* pkChild = &pkBlock[usChild];
        pkChild->Initialize(pkPage,pkBlock,usChild,ucX,ucY,ucChildStride,
            true);

        // process child 01
        usChild++;
        pkChild++;
        pkChild->Initialize(pkPage,pkBlock,usChild,ucX+ucStride,ucY,
            ucChildStride,false);

        // process child 10
        usChild++;
        pkChild++;
        pkChild->Initialize(pkPage,pkBlock,usChild,ucX,ucY+ucStride,
            ucChildStride,false);

        // process child 11
        usChild++;
        pkChild++;
        pkChild->Initialize(pkPage,pkBlock,usChild,ucX+ucStride,ucY+ucStride,
            ucChildStride,true);
    }
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::UpdateBoundingBox (MgcTerrainPage* pkPage,
    MgcTerrainBlock* pkBlock, unsigned short usBlock, unsigned char ucStride)
{
    MgcVector3 akPoint[9];
    akPoint[0].x = pkPage->GetX(m_ucX);
    akPoint[0].y = pkPage->GetY(m_ucY);
    akPoint[1].x = pkPage->GetX(m_ucX + m_ucStride);
    akPoint[1].y = akPoint[0].y;
    akPoint[2].x = pkPage->GetX(m_ucX + 2*m_ucStride);
    akPoint[2].y = akPoint[0].y;
    akPoint[3].x = akPoint[0].x;
    akPoint[3].y = pkPage->GetY(m_ucY + m_ucStride);
    akPoint[4].x = akPoint[1].x;
    akPoint[4].y = akPoint[3].y;
    akPoint[5].x = akPoint[2].x;
    akPoint[5].y = akPoint[3].y;
    akPoint[6].x = akPoint[0].x;
    akPoint[6].y = pkPage->GetY(m_ucY + 2*m_ucStride);
    akPoint[7].x = akPoint[1].x;
    akPoint[7].y = akPoint[6].y;
    akPoint[8].x = akPoint[2].x;
    akPoint[8].y = akPoint[6].y;

    unsigned short usOrigin = m_ucX + pkPage->m_usSize*m_ucY;
    akPoint[0].z = pkPage->GetHeight(usOrigin);
    akPoint[1].z = pkPage->GetHeight(usOrigin+ucStride);
    akPoint[2].z = pkPage->GetHeight(usOrigin+2*ucStride);
    usOrigin += pkPage->m_usSize*ucStride;
    akPoint[3].z = pkPage->GetHeight(usOrigin);
    akPoint[4].z = pkPage->GetHeight(usOrigin+ucStride);
    akPoint[5].z = pkPage->GetHeight(usOrigin+2*ucStride);
    usOrigin += pkPage->m_usSize*ucStride;
    akPoint[6].z = pkPage->GetHeight(usOrigin);
    akPoint[7].z = pkPage->GetHeight(usOrigin+ucStride);
    akPoint[8].z = pkPage->GetHeight(usOrigin+2*ucStride);

    // compute (x,y) components of bounding box
    m_kMin.x = akPoint[0].x;
    m_kMin.y = akPoint[0].y;
    m_kMax.x = akPoint[8].x;
    m_kMax.y = akPoint[8].y;
    
    // compute delta max
    MgcReal fC0 = akPoint[0].z;
    MgcReal fMd = akPoint[1].z;
    MgcReal fC1 = akPoint[2].z;
    m_fDelta[0] = 0.5*(fC0+fC1)-fMd;
    m_fDelta[0] *= m_fDelta[0];
    
    fC0 = akPoint[8].z;
    fMd = akPoint[5].z;
    m_fDelta[1] = 0.5*(fC0+fC1)-fMd;
    m_fDelta[1] *= m_fDelta[1];
    
    fMd = akPoint[7].z;
    fC1 = akPoint[6].z;
    m_fDelta[2] = 0.5*(fC0+fC1)-fMd;
    m_fDelta[2] *= m_fDelta[2];
    
    fC0 = akPoint[0].z;
    fMd = akPoint[3].z;
    m_fDelta[3] = 0.5*(fC0+fC1)-fMd;
    m_fDelta[3] *= m_fDelta[3];
    
    fMd = akPoint[4].z;
    if ( GetEven() )
    {
        fC0 = akPoint[2].z;
        fC1 = akPoint[6].z;
    }
    else
    {
        fC0 = akPoint[0].z;
        fC1 = akPoint[8].z;
    }
    m_fDelta[4] = 0.5*(fC0+fC1)-fMd;
    m_fDelta[4] *= m_fDelta[4];

    m_fDeltaMax = m_fDelta[0];
    for (int i = 1; i < 5; i++)
    {
        if ( m_fDelta[i] > m_fDeltaMax )
            m_fDeltaMax = m_fDelta[i];
    }

    // recurse on children (if any)
    if ( ucStride > 1 )
    {
        // child stride is half the parent stride
        unsigned char ucChildStride = ( ucStride >> 1 );

        // process child 00
        unsigned short usChild = GetChildIndex(usBlock,1);
        MgcTerrainBlock* pkChild = &pkBlock[usChild];
        pkChild->UpdateBoundingBox(pkPage,pkBlock,usChild,ucChildStride);
        if ( pkChild->m_fDeltaMax > m_fDeltaMax )
            m_fDeltaMax = pkChild->m_fDeltaMax;
        m_kMin.z = pkChild->m_kMin.z;
        m_kMax.z = pkChild->m_kMax.z;

        // process child 01
        usChild++;
        pkChild++;
        pkChild->UpdateBoundingBox(pkPage,pkBlock,usChild,ucChildStride);
        if ( pkChild->m_fDeltaMax > m_fDeltaMax )
            m_fDeltaMax = pkChild->m_fDeltaMax;
        if ( pkChild->m_kMin.z < m_kMin.z )
            m_kMin.z = pkChild->m_kMin.z;
        if ( pkChild->m_kMax.z > m_kMax.z )
            m_kMax.z = pkChild->m_kMax.z;

        // process child 10
        usChild++;
        pkChild++;
        pkChild->UpdateBoundingBox(pkPage,pkBlock,usChild,ucChildStride);
        if ( pkChild->m_fDeltaMax > m_fDeltaMax )
            m_fDeltaMax = pkChild->m_fDeltaMax;
        if ( pkChild->m_kMin.z < m_kMin.z )
            m_kMin.z = pkChild->m_kMin.z;
        if ( pkChild->m_kMax.z > m_kMax.z )
            m_kMax.z = pkChild->m_kMax.z;

        // process child 11
        usChild++;
        pkChild++;
        pkChild->UpdateBoundingBox(pkPage,pkBlock,usChild,ucChildStride);
        if ( pkChild->m_fDeltaMax > m_fDeltaMax )
            m_fDeltaMax = pkChild->m_fDeltaMax;
        if ( pkChild->m_kMin.z < m_kMin.z )
            m_kMin.z = pkChild->m_kMin.z;
        if ( pkChild->m_kMax.z > m_kMax.z )
            m_kMax.z = pkChild->m_kMax.z;
    }
    else
    {
        // compute z components of bounding box at leaf node of quadtree
        m_kMin.z = akPoint[0].z;
        m_kMax.z = m_kMin.z;
        for (unsigned short usIndex = 1; usIndex < 9; usIndex++)
        {
            MgcReal fZ = akPoint[usIndex].z;
            if ( fZ < m_kMin.z )
                m_kMin.z = fZ;
            if ( fZ > m_kMax.z )
                m_kMax.z = fZ;
        }
    }
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::ComputeInterval (const MgcVector3& rkModelEye,
    MgcReal fTolerance)
{
    // distant terrain assumption

    if ( fTolerance > 0.0 )
    {
        // compute hmin = |eye.z - clamp(bmin.z,eye.z,bmax.z)|
        MgcReal fHMin;
        if ( rkModelEye.z < m_kMin.z )
        {
            fHMin = rkModelEye.z - m_kMin.z;
            fHMin *= fHMin;
        }
        else if ( rkModelEye.z > m_kMax.z )
        {
            fHMin = rkModelEye.z - m_kMax.z;
            fHMin *= fHMin;
        }
        else
        {
            fHMin = 0.0;
        }

        // compute hmax = max{|eye.z - bmin.z|,|eye.z - bmax.z|}
        MgcReal fHMax = rkModelEye.z - m_kMin.z;
        fHMax *= fHMax;
        MgcReal fTmp = rkModelEye.z - m_kMax.z;
        fTmp *= fTmp;
        if ( fTmp > fHMax )
            fHMax = fTmp;

        // compute rmin and rmax
        MgcReal fDxMin = rkModelEye.x - m_kMin.x;
        MgcReal fDxMax = rkModelEye.x - m_kMax.x;
        MgcReal fDyMin = rkModelEye.y - m_kMin.y;
        MgcReal fDyMax = rkModelEye.y - m_kMax.y;
        fDxMin *= fDxMin;
        fDxMax *= fDxMax;
        fDyMin *= fDyMin;
        fDyMax *= fDyMax;
        MgcReal fRMin = 0.0, fRMax = 0.0;

        if ( rkModelEye.x < m_kMin.x )
        {
            fRMin += fDxMin;
            fRMax += fDxMax;
        }
        else if ( rkModelEye.x <= m_kMax.x )
        {
            fRMax += ( fDxMax >= fDxMin ? fDxMax : fDxMin );
        }
        else
        {
            fRMin += fDxMax;
            fRMax += fDxMin;
        }

        if ( rkModelEye.y < m_kMin.y )
        {
            fRMin += fDyMin;
            fRMax += fDyMax;
        }
        else if ( rkModelEye.y <= m_kMax.y )
        {
            fRMax += ( fDyMax >= fDyMin ? fDyMax : fDyMin );
        }
        else
        {
            fRMin += fDyMax;
            fRMax += fDyMin;
        }

        // compute fmin
        MgcReal fDenom = fRMin + fHMax;
        MgcReal fFMin =
            (fDenom > 0.0 ? fRMin/(fDenom*fDenom) : MgcMath::INFINITY);
        fDenom = fRMax + fHMax;
        fTmp = (fDenom > 0.0 ? fRMax/(fDenom*fDenom) : MgcMath::INFINITY);
        if ( fTmp < fFMin )
            fFMin = fTmp;
        
        // compute fmax
        MgcReal fFMax;
        if ( fRMin >= fHMin )
        {
            fDenom = fRMin + fHMin;
            fFMax =
                (fDenom > 0.0 ? fRMin/(fDenom*fDenom) : MgcMath::INFINITY);
        }
        else if ( fRMax <= fHMin )
        {
            fDenom = fRMax + fHMin;
            fFMax =
                (fDenom > 0.0 ? fRMax/(fDenom*fDenom) : MgcMath::INFINITY);
        }
        else
        {
            fFMax = (fHMin > 0.0 ? 0.25/fHMin : MgcMath::INFINITY);
        }
        
        m_fDeltaL = fTolerance/fFMax;
        m_fDeltaH = (fFMin > 0.0 ? fTolerance/fFMin : MgcMath::INFINITY);
    }
    else  // fTolerance == 0.0
    {
        m_fDeltaL = 0.0;
        m_fDeltaH = MgcMath::INFINITY;
    }
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::ComputeInterval (const MgcVector3& rkModelEye,
    const MgcVector3& rkModelDir, MgcReal fTolerance, MgcVector2& rkLoc,
    MgcReal fSpacing)
{
    // close terrain assumption

    if ( fTolerance > 0.0 )
    {
        // compute fmin and fmax

        // temporary quantities
        MgcReal fLmEx = rkLoc.x - rkModelEye.x;
        MgcReal fLmEy = rkLoc.y - rkModelEye.y;
        MgcReal fTmp = fSpacing*MgcReal(m_ucStride);
        MgcReal fXSum = fLmEx + fTmp;
        MgcReal fYSum = fLmEy + fTmp;
        MgcReal fXDif = fLmEx - fTmp;
        MgcReal fYDif = fLmEy - fTmp;

        // find corners of block closest to and farthest from eye
        MgcReal fFMin = MgcMath::Abs(rkModelDir.x*fXDif + rkModelDir.y*fYDif);
        MgcReal fFMax = fFMin;

        fTmp = MgcMath::Abs(rkModelDir.x*fXSum + rkModelDir.y*fYDif);
        if ( fTmp >= fFMin )
            fFMin = fTmp;
        else 
            fFMax = fTmp;

        fTmp = MgcMath::Abs(rkModelDir.x*fXSum + rkModelDir.y*fYSum);
        if ( fTmp >= fFMin )
            fFMin = fTmp;
        else 
            fFMax = fTmp;

        fTmp = MgcMath::Abs(rkModelDir.x*fXDif + rkModelDir.y*fYSum);
        if ( fTmp >= fFMin )
            fFMin = fTmp;
        else
            fFMax = fTmp;

        m_fDeltaL = fTolerance*fFMax;
        m_fDeltaH = fTolerance*fFMin;
    }
    else  // fTolerance == 0.0
    {
        m_fDeltaL = 0.0;
        m_fDeltaH = MgcMath::INFINITY;
    }
}
//---------------------------------------------------------------------------
bool MgcTerrainBlock::TestIntersect (const MgcBox3& rkBox,
    const MgcFrustum& rkFrustum)
{
    // for convenience
    const MgcVector3* akA = rkBox.Axes();
    const MgcReal* afE = rkBox.Extents();

    MgcVector3 kDiff = rkBox.Center() - rkFrustum.Origin();

    MgcReal afA[3], afB[3], afC[3], afD[3];
    MgcReal afNA[3], afNB[3], afNC[3], afND[3];
    MgcReal afNApLC[3], afNAmLC[3], afNBpUC[3], afNBmUC[3];
    MgcReal afLC[3], afLD[3], afUC[3], afUD[3], afLBpUA[3], afLBmUA[3];
    MgcReal fDdD, fR, fP, fMin, fMax, fMTwoLF, fMTwoUF, fLB, fUA, fTmp;
    int i, j;

    // M = D
    afD[2] = kDiff.Dot(rkFrustum.DVector());
    for (i = 0; i < 3; i++)
        afC[i] = akA[i].Dot(rkFrustum.DVector());
    fR = afE[0]*MgcMath::Abs(afC[0]) +
         afE[1]*MgcMath::Abs(afC[1]) +
         afE[2]*MgcMath::Abs(afC[2]);
    if ( afD[2] + fR < rkFrustum.DMin() || afD[2] - fR > rkFrustum.DMax() )
        return false;

    // M = n*L - l*D
    for (i = 0; i < 3; i++)
    {
        afA[i] = akA[i].Dot(rkFrustum.LVector());
        afLC[i] = rkFrustum.LBound()*afC[i];
        afNA[i] = rkFrustum.DMin()*afA[i];
        afNAmLC[i] = afNA[i] - afLC[i];
    }
    afD[0] = kDiff.Dot(rkFrustum.LVector());
    fR = afE[0]*MgcMath::Abs(afNAmLC[0]) +
         afE[1]*MgcMath::Abs(afNAmLC[1]) +
         afE[2]*MgcMath::Abs(afNAmLC[2]);
    afND[0] = rkFrustum.DMin()*afD[0];
    afLD[2] = rkFrustum.LBound()*afD[2];
    fDdD = afND[0] - afLD[2];
    fMTwoLF = rkFrustum.GetMTwoLF();
    if ( fDdD + fR < fMTwoLF || fDdD > fR )
        return false;

    // M = -n*L - l*D
    for (i = 0; i < 3; i++)
        afNApLC[i] = afNA[i] + afLC[i];
    fR = afE[0]*MgcMath::Abs(afNApLC[0]) +
         afE[1]*MgcMath::Abs(afNApLC[1]) +
         afE[2]*MgcMath::Abs(afNApLC[2]);
    fDdD = -(afND[0] + afLD[2]);
    if ( fDdD + fR < fMTwoLF || fDdD > fR )
        return false;

    // M = n*U - u*D
    for (i = 0; i < 3; i++)
    {
        afB[i] = akA[i].Dot(rkFrustum.UVector());
        afUC[i] = rkFrustum.UBound()*afC[i];
        afNB[i] = rkFrustum.DMin()*afB[i];
        afNBmUC[i] = afNB[i] - afUC[i];
    }
    afD[1] = kDiff.Dot(rkFrustum.UVector());
    fR = afE[0]*MgcMath::Abs(afNBmUC[0]) +
         afE[1]*MgcMath::Abs(afNBmUC[1]) +
         afE[2]*MgcMath::Abs(afNBmUC[2]);
    afND[1] = rkFrustum.DMin()*afD[1];
    afUD[2] = rkFrustum.UBound()*afD[2];
    fDdD = afND[1] - afUD[2];
    fMTwoUF = rkFrustum.GetMTwoUF();
    if ( fDdD + fR < fMTwoUF || fDdD > fR )
        return false;

    // M = -n*U - u*D
    for (i = 0; i < 3; i++)
        afNBpUC[i] = afNB[i] + afUC[i];
    fR = afE[0]*MgcMath::Abs(afNBpUC[0]) +
         afE[1]*MgcMath::Abs(afNBpUC[1]) +
         afE[2]*MgcMath::Abs(afNBpUC[2]);
    fDdD = -(afND[1] + afUD[2]);
    if ( fDdD + fR < fMTwoUF || fDdD > fR )
        return false;

    // M = A[i]
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.LBound()*MgcMath::Abs(afA[i]) +
             rkFrustum.UBound()*MgcMath::Abs(afB[i]);
        afNC[i] = rkFrustum.DMin()*afC[i];
        fMin = afNC[i] - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = afNC[i] + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = afA[i]*afD[0] + afB[i]*afD[1] + afC[i]*afD[2];
        if ( fDdD + afE[i] < fMin || fDdD - afE[i] > fMax )
            return false;
    }

    // M = Cross(L,A[i])
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.UBound()*MgcMath::Abs(afC[i]);
        fMin = afNB[i] - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = afNB[i] + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = -afC[i]*afD[1] + afB[i]*afD[2];
        fR = afE[0]*MgcMath::Abs(afB[i]*afC[0]-afB[0]*afC[i]) +
             afE[1]*MgcMath::Abs(afB[i]*afC[1]-afB[1]*afC[i]) +
             afE[2]*MgcMath::Abs(afB[i]*afC[2]-afB[2]*afC[i]);
        if ( fDdD + fR < fMin || fDdD - fR > fMax )
            return false;
    }

    // M = Cross(U,A[i])
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.LBound()*MgcMath::Abs(afC[i]);
        fMin = -afNA[i] - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = -afNA[i] + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = afC[i]*afD[0] - afA[i]*afD[2];
        fR = afE[0]*MgcMath::Abs(afA[i]*afC[0]-afA[0]*afC[i]) +
             afE[1]*MgcMath::Abs(afA[i]*afC[1]-afA[1]*afC[i]) +
             afE[2]*MgcMath::Abs(afA[i]*afC[2]-afA[2]*afC[i]);
        if ( fDdD + fR < fMin || fDdD - fR > fMax )
            return false;
    }

    // M = Cross(n*D+l*L+u*U,A[i])
    for (i = 0; i < 3; i++)
    {
        fLB = rkFrustum.LBound()*afB[i];
        fUA = rkFrustum.UBound()*afA[i];
        afLBpUA[i] = fLB + fUA;
        afLBmUA[i] = fLB - fUA;
    }
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.LBound()*MgcMath::Abs(afNBmUC[i]) +
             rkFrustum.UBound()*MgcMath::Abs(afNAmLC[i]);
        fTmp = rkFrustum.DMin()*afLBmUA[i];
        fMin = fTmp - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = fTmp + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = -afD[0]*afNBmUC[i] + afD[1]*afNAmLC[i] + afD[2]*afLBmUA[i];
        fR = 0.0;
        for (j = 0; j < 3; j++)
        {
            fR += afE[j]*MgcMath::Abs(-afA[j]*afNBmUC[i]+ afB[j]*afNAmLC[i]
                + afC[j]*afLBmUA[i]);
        }
        if ( fDdD + fR < fMin || fDdD - fR > fMax )
            return false;
    }

    // M = Cross(n*D+l*L-u*U,A[i])
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.LBound()*MgcMath::Abs(afNBpUC[i]) +
             rkFrustum.UBound()*MgcMath::Abs(afNAmLC[i]);
        fTmp = rkFrustum.DMin()*afLBpUA[i];
        fMin = fTmp - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = fTmp + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = -afD[0]*afNBpUC[i] + afD[1]*afNAmLC[i] + afD[2]*afLBpUA[i];
        fR = 0.0;
        for (j = 0; j < 3; j++)
        {
            fR += afE[j]*MgcMath::Abs(-afA[j]*afNBpUC[i]+ afB[j]*afNAmLC[i]
                + afC[j]*afLBpUA[i]);
        }
        if ( fDdD + fR < fMin || fDdD - fR > fMax )
            return false;
    }

    // M = Cross(n*D-l*L+u*U,A[i])
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.LBound()*MgcMath::Abs(afNBmUC[i]) +
             rkFrustum.UBound()*MgcMath::Abs(afNApLC[i]);
        fTmp = -rkFrustum.DMin()*afLBpUA[i];
        fMin = fTmp - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = fTmp + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = -afD[0]*afNBmUC[i] + afD[1]*afNApLC[i] - afD[2]*afLBpUA[i];
        fR = 0.0;
        for (j = 0; j < 3; j++)
        {
            fR += afE[j]*MgcMath::Abs(-afA[j]*afNBmUC[i]+ afB[j]*afNApLC[i]
                - afC[j]*afLBpUA[i]);
        }
        if ( fDdD + fR < fMin || fDdD - fR > fMax )
            return false;
    }

    // M = Cross(n*D-l*L-u*U,A[i])
    for (i = 0; i < 3; i++)
    {
        fP = rkFrustum.LBound()*MgcMath::Abs(afNBpUC[i]) +
             rkFrustum.UBound()*MgcMath::Abs(afNApLC[i]);
        fTmp = -rkFrustum.DMin()*afLBmUA[i];
        fMin = fTmp - fP;
        if ( fMin < 0.0 )
            fMin *= rkFrustum.GetDRatio();
        fMax = fTmp + fP;
        if ( fMax > 0.0 )
            fMax *= rkFrustum.GetDRatio();
        fDdD = -afD[0]*afNBpUC[i] + afD[1]*afNApLC[i] - afD[2]*afLBmUA[i];
        fR = 0.0;
        for (j = 0; j < 3; j++)
        {
            fR += afE[j]*MgcMath::Abs(-afA[j]*afNBpUC[i]+ afB[j]*afNApLC[i]
                - afC[j]*afLBmUA[i]);
        }
        if ( fDdD + fR < fMin || fDdD - fR > fMax )
            return false;
    }

    return true;
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::TestIntersectFrustum (const MgcTerrainPage* pPage,
    const MgcCamera* pkCamera)
{
    SetVisibilityTested(true);

    // centered-form bounding box of page in terrain model space
    MgcBox3 kBox;
    kBox.Center() = 0.5*(m_kMin + m_kMax);
    kBox.Extent(0) = 0.5*(m_kMax.x - m_kMin.x);
    kBox.Extent(1) = 0.5*(m_kMax.y - m_kMin.y);
    kBox.Extent(2) = 0.5*(m_kMax.z - m_kMin.z);
    kBox.Axis(0) = MgcVector3::UNIT_X;
    kBox.Axis(1) = MgcVector3::UNIT_Y;
    kBox.Axis(2) = MgcVector3::UNIT_Z;

    // inverse transform to camera space
    MgcVector3 kDiff = kBox.Center() - pkCamera->GetLocation();
    kBox.Center() = MgcVector3(kDiff.Dot(pkCamera->GetLeft()),
        kDiff.Dot(pkCamera->GetUp()),kDiff.Dot(pkCamera->GetDirection()));
    kBox.Axis(0) = MgcVector3(pkCamera->GetLeft().x,pkCamera->GetUp().x,
        pkCamera->GetDirection().x);
    kBox.Axis(1) = MgcVector3(pkCamera->GetLeft().y,pkCamera->GetUp().y,
        pkCamera->GetDirection().y);
    kBox.Axis(2) = MgcVector3(pkCamera->GetLeft().z,pkCamera->GetUp().z,
        pkCamera->GetDirection().z);

    // default frustum matches camera coordinate frame
    MgcFrustum kFrustum;
    kFrustum.LBound() = pkCamera->GetFrustumRight();
    kFrustum.UBound() = pkCamera->GetFrustumTop();
    kFrustum.DMin() = pkCamera->GetFrustumNear();
    kFrustum.DMax() = pkCamera->GetFrustumFar();
    kFrustum.Update();

    SetVisible(TestIntersect(kBox,kFrustum));
    //SetVisible(true);
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::SimplifyVertices (MgcTerrainPage* pkPage,
    const MgcVector3& rkModelEye, const MgcVector3& rkModelDir,
    MgcReal fTolerance, bool bCloseAssumption)
{
    unsigned short usSize = pkPage->m_usSize;
    unsigned short usOrigin = m_ucX + usSize*m_ucY;
    MgcTerrainVertex* pkVOrigin = pkPage->m_akTVertex + usOrigin;
    MgcTerrainVertex* pkTVertex;
    unsigned short usOffset;
    MgcVector3 kDiff;
    MgcReal fRSqr, fLenSqr, fDistDir;

    // simplify at (stride,0)
    if ( m_fDeltaL <= m_fDelta[0] )
    {
        pkTVertex = pkVOrigin + m_ucStride;
        if ( m_fDelta[0] <= m_fDeltaH )
        {
            // test vertex delta against tolerance
            if ( !pkTVertex->GetEnabled() )
            {
                kDiff.x = rkModelEye.x - pkPage->GetX(m_ucX+m_ucStride);
                kDiff.y = rkModelEye.y - pkPage->GetY(m_ucY);
                if ( bCloseAssumption ) 
                {
                    fDistDir = rkModelDir.x*kDiff.x + rkModelDir.y*kDiff.y;
                    if ( m_fDelta[0] > fTolerance*fDistDir*fDistDir )
                        pkTVertex->Enable();
                }
                else // distant assumption
                {
                    kDiff.z = rkModelEye.z -
                        pkPage->GetHeight(usOrigin+m_ucStride);
                    fRSqr = kDiff.x*kDiff.x + kDiff.y*kDiff.y;
                    fLenSqr = fRSqr + kDiff.z*kDiff.z;
                    if ( m_fDelta[0]*fRSqr > fTolerance*fLenSqr*fLenSqr )
                        pkTVertex->Enable();
                }
            }
        }
        else
        {
            if ( !pkTVertex->GetEnabled() )
                pkTVertex->Enable();
        }
    }

    // simplify at (2*stride,stride)
    if ( m_fDeltaL <= m_fDelta[1] )
    {
        usOffset = (usSize+2)*m_ucStride;
        pkTVertex = pkVOrigin + usOffset;
        if ( m_fDelta[1] <= m_fDeltaH )
        {
            // test vertex delta against tolerance
            if ( !pkTVertex->GetEnabled() )
            {
                kDiff.x = rkModelEye.x - pkPage->GetX(m_ucX+2*m_ucStride);
                kDiff.y = rkModelEye.y - pkPage->GetY(m_ucY+m_ucStride);
                if ( bCloseAssumption ) 
                {
                    fDistDir = rkModelDir.x*kDiff.x + rkModelDir.y*kDiff.y;
                    if ( m_fDelta[1] > fTolerance*fDistDir*fDistDir )
                        pkTVertex->Enable();
                }
                else // distant assumption
                {
                    kDiff.z = rkModelEye.z -
                        pkPage->GetHeight(usOrigin+usOffset);
                    fRSqr = kDiff.x*kDiff.x + kDiff.y*kDiff.y;
                    fLenSqr = fRSqr + kDiff.z*kDiff.z;
                    if ( m_fDelta[1]*fRSqr > fTolerance*fLenSqr*fLenSqr )
                        pkTVertex->Enable();
                }
            }
        }
        else
        {
            if ( !pkTVertex->GetEnabled() )
            {
                pkTVertex->Enable();
            }
        }
    }

    // simplify at (stride,2*stride)
    if ( m_fDeltaL <= m_fDelta[2] )
    {
        usOffset = (2*usSize+1)*m_ucStride;
        pkTVertex = pkVOrigin + usOffset;
        if ( m_fDelta[2] <= m_fDeltaH )
        {
            // test vertex delta against tolerance
            if ( !pkTVertex->GetEnabled() )
            {
                kDiff.x = rkModelEye.x - pkPage->GetX(m_ucX+m_ucStride);
                kDiff.y = rkModelEye.y - pkPage->GetY(m_ucY+2*m_ucStride);
                if ( bCloseAssumption ) 
                {
                    fDistDir = rkModelDir.x*kDiff.x + rkModelDir.y*kDiff.y;
                    if ( m_fDelta[2] > fTolerance*fDistDir*fDistDir )
                        pkTVertex->Enable();
                }
                else // distant assumption
                {
                    kDiff.z = rkModelEye.z -
                        pkPage->GetHeight(usOrigin+usOffset);
                    fRSqr = kDiff.x*kDiff.x + kDiff.y*kDiff.y;
                    fLenSqr = fRSqr + kDiff.z*kDiff.z;
                    if ( m_fDelta[2]*fRSqr > fTolerance*fLenSqr*fLenSqr )
                        pkTVertex->Enable();
                }
            }
        }
        else
        {
            if ( !pkTVertex->GetEnabled() )
                pkTVertex->Enable();
        }
    }

    // simplify at (0,stride)
    if ( m_fDeltaL <= m_fDelta[3] )
    {
        usOffset = usSize*m_ucStride;
        pkTVertex = pkVOrigin + usOffset;
        if ( m_fDelta[3] <= m_fDeltaH )
        {
            // test vertex delta against tolerance
            if ( !pkTVertex->GetEnabled() )
            {
                kDiff.x = rkModelEye.x - pkPage->GetX(m_ucX);
                kDiff.y = rkModelEye.y - pkPage->GetY(m_ucY+m_ucStride);
                if ( bCloseAssumption ) 
                {
                    fDistDir = rkModelDir.x*kDiff.x + rkModelDir.y*kDiff.y;
                    if ( m_fDelta[3] > fTolerance*fDistDir*fDistDir )
                        pkTVertex->Enable();
                }
                else // distant terrain assumption
                {
                    kDiff.z = rkModelEye.z -
                        pkPage->GetHeight(usOrigin+usOffset);
                    fRSqr = kDiff.x*kDiff.x + kDiff.y*kDiff.y;
                    fLenSqr = fRSqr + kDiff.z*kDiff.z;
                    if ( m_fDelta[3]*fRSqr > fTolerance*fLenSqr*fLenSqr )
                        pkTVertex->Enable();
                }
            }
        }
        else
        {
            if ( !pkTVertex->GetEnabled() )
                pkTVertex->Enable();
        }
    }

    // simplify at (stride,stride)
    if ( m_fDeltaL <= m_fDelta[4] )
    {
        usOffset = (usSize+1)*m_ucStride;
        pkTVertex = pkVOrigin + usOffset;
        if ( m_fDelta[4] <= m_fDeltaH )
        {
            // test vertex delta against tolerance
            if ( !pkTVertex->GetEnabled() )
            {
                kDiff.x = rkModelEye.x - pkPage->GetX(m_ucX+m_ucStride);
                kDiff.y = rkModelEye.y - pkPage->GetY(m_ucY+m_ucStride);
                if ( bCloseAssumption ) 
                {
                    fDistDir = rkModelDir.x*kDiff.x + rkModelDir.y*kDiff.y;
                    if ( m_fDelta[4] > fTolerance*fDistDir*fDistDir )
                        pkTVertex->Enable();
                }
                else // distant terrain assumption
                {
                    kDiff.z = rkModelEye.z -
                        pkPage->GetHeight(usOrigin+usOffset);
                    fRSqr = kDiff.x*kDiff.x + kDiff.y*kDiff.y;
                    fLenSqr = fRSqr + kDiff.z*kDiff.z;
                    if ( m_fDelta[4]*fRSqr > fTolerance*fLenSqr*fLenSqr )
                        pkTVertex->Enable();
                }
            }
        }
        else
        {
            if ( !pkTVertex->GetEnabled() )
                pkTVertex->Enable();
        }
    }

    // enable the corner vertices
    if ( GetEven() )
    {
        pkTVertex = pkVOrigin + 2*m_ucStride;
        if ( !pkTVertex->GetEnabled() )
            pkTVertex->Enable();

        pkTVertex = pkVOrigin + 2*usSize*m_ucStride;
        if ( !pkTVertex->GetEnabled() )
            pkTVertex->Enable();
    }
    else
    {
        pkTVertex = pkVOrigin;
        if ( !pkTVertex->GetEnabled() )
            pkTVertex->Enable();

        pkTVertex = pkVOrigin + 2*(usSize+1)*m_ucStride;
        if ( !pkTVertex->GetEnabled() )
            pkTVertex->Enable();
    }
}
//---------------------------------------------------------------------------
void MgcTerrainBlock::Disable (MgcTerrainPage* pkPage)
{
    MgcTerrainVertex* akTVertex[9];
    GetVertex9(pkPage->m_usSize,pkPage->m_akTVertex,akTVertex);
    for (int i = 0; i < 9; i++)
    {
        if ( akTVertex[i]->GetEnabled() )
            akTVertex[i]->Disable();
    }
}
//---------------------------------------------------------------------------
